Teorema de Post

Na teoria da computação, o Teorema de Post,em homenagem à Emil Post, descreve a conexão entre hierarquia aritmética e os graus de Turing.

Background

A demonstração do teorema de Post usa vários conceitos relativos à definibilidade e teoria da recursão. Esta seção apresenta uma visão geral desses conceitos, que são abordados em profundidade em seus respectivos artigos.

A hierarquia aritmética classifica os conjuntos de números naturais que são definíveis na linguagem da aritmética de Peano. Uma fórmula é dita ser $\Sigma _{m}^{0}$ se é uma afirmação existencial na forma normal prenex (todos os quantificadores na frente) com $m$ alternâncias entre quantificadores existenciais e universais aplicadas a uma fórmula livre de quantificador Formalmente uma fórmula $\phi (s)$ na linguagem da aritmética de Peano é uma $\Sigma _{m}^{0}$ fórmula se ele é da forma

\exists n_{1}\forall n_{2}\exists n_{3}\forall n_{4}\cdots Qn_{m}\rho (n_{1},\ldots ,n_{m},x_{1},\ldots ,x_{k}),

onde ρ é uma fórmula livre quantificador e Q é $\forall$ se m é par e $\exists$ se m é impar. Note-se que qualquer fórmula na forma

\left(\exists n_{1}^{1}\exists n_{2}^{1}\cdots \exists n_{j_{1}}^{1}\right)\left(\forall n_{1}^{2}\cdots \forall n_{j_{2}}^{2}\right)\left(\exists n_{1}^{3}\cdots \right)\cdots \left(Q_{1}n_{1}^{m}\cdots \right)\rho (n_{1}^{1},\ldots n_{j_{m}}^{m},x_{1},\ldots ,x_{k})

Onde $\rho$ contém apenas quantificadores delimitados é comprovadamente equivalente a uma fórmula da forma acima dos axiomas da Aritmética de Peano. Assim, não é incomum ver $\Sigma _{m}^{0}$ fórmulas definidas nesta forma alternativa e não equivalentes tecnicamente, já que na prática a distinção raramente é importante.

Um conjunto de números naturais A é dito ser $\Sigma _{m}^{0}$ se é definida por uma $\Sigma _{m}^{0}$ fórmula, isto é, se houver uma $\Sigma _{m}^{0}$ fórmula $\phi (s)$ tal que cada número n está em A, se e somente se $\phi (n)$ detém. Sabe-se que, se um conjunto é $\Sigma _{m}^{0}$ então ele é $\Sigma _{n}^{0}$ para cada $n>m$ , mas para cada m existe um $\Sigma _{m+1}^{0}$ conjunto que não é $\Sigma _{m}^{0}$ . Assim, o número de quantificadores alternados necessários para definir um conjunto dá uma medida da complexidade do conjunto.

O teorema de Post usa a hierarquia aritmética relativizada, bem como a hierarquia não relativizada apenas definida. Um conjunto A' de números naturais é dito ser $\Sigma _{m}^{0}$ relativo à um conjunto B, escrito $\Sigma _{m}^{0,B}$ , se A é definível por uma $\Sigma _{m}^{0}$ fórmula em uma linguagem estendida que inclui um predicado para a adesão em B.

Enquanto a hierarquia aritmética mede definibilidade de conjuntos de números naturais, graus de Turing medem o nível de não computabilidade do conjunto dos números naturais. Um conjunto A é dito ser Turing redutível à um conjunto B, escrito $A\leq _{T}B$ , se existe uma máquina de Turing oráculo tal que, dado um oráculo para B, compute as funções características de A. O salto de Turing de um conjunto A é uma forma do problema da parada relativo à A. Dado um conjunto A, O salto de Turing $A'$ é o conjunto de índices da máquina de turing oráculo que para na entrada 0 quando computando com o oráculo A. Sabemos que todo conjunto A é Turing redutível para o seu salto de Turing, mas o salto de Turing de um conjunto nunca é Turing redutível ao seu conjunto original.

O teorema de Post usa infinitos saltos iterados de Turing . Para qualquer conjunto A nos números naturais a notação $A^{(n)}$ indica a "n"-vezes reiterou o salto de Turing de A Assim $A^{(0)}$ é apenas A, e $A^{(n+1)}$ é o salto de Turing de $A^{(n)}$ .

Teorema de Post e corolários

O teorema de Post's estabelece uma conexão próxima entre a hierarquia aritmética e os graus de turing da forma $\emptyset ^{(n)}$ , que é, finitos saltos iterados de Turing do conjunto vazio. (O conjunto vazio pode ser substituído por qualquer outro conjunto computável sem que haja mudança na definição do teorema).

Estados do teorema de Post :

Um conjunto B é $\Sigma _{n+1}^{0}$ se e somente se $B$ é recursivamente enumerável por uma máquina de Turing oráculo, com um oraculo para $\emptyset ^{(n)}$ , ou seja, se e somente se B é $\Sigma _{1}^{0,\emptyset ^{(n)}}$ .
O conjunto $\emptyset ^{(n)}$ é $\Sigma _{n}^{0}$ completo para cada $n>0$ . Isso significa que cada $\Sigma _{n}^{0}$ conjunto é redutível em muitos para um para $\emptyset ^{(n)}$ .

O teorema de Post possui muitos corolários que mostram relações adicionais entre hierarquia aritmética e os graus de Turing. Os quais incluem:

Ajustar um conjunto C. Um conjunto B é $\Sigma _{n+1}^{0,C}$ se e somente se B é $\Sigma _{1}^{0,C^{(n)}}$ . Esta é a relativização da primeira parte do teorema de Post para o oráculo C.
Um conjunto B é $\Delta _{n+1}$ se e somente se $B\leq _{T}\emptyset ^{(n)}$ . Mais genericamente, B é $\Delta _{n+1}^{C}$ se e somente se $B\leq _{T}C^{(n)}$ .
Um conjunto é dito ser aritmético se ele é $\Sigma _{n}^{0}$ para algum n. O teorema de Post mostra que , equivalentemente, um conjunto é aritmético se e somente se ele é Turing redutível à $\emptyset ^{(m)}$ para algum m.